検証可能秘密分散法:VSS(verifiable secret sharing)
1.VSSの概要
検証可能秘密分散法は、ディーラーが悪意を持っていたとしても、復元するプレーヤーの組によらず、必ず同じ秘密情報が復元されることを保証できる。
どんな用途があるの？
MPCなどで使用される
なにが検証可能なの？
持っているshareからsecretを復元できるかどうか、言い換えるとshareが多項式上にあるかどうかを検証している
Feldman VSSとPederson VSSが有名で、どちらも離散対数問題を安全性の根拠に置いている。
2.Feldman's VSS
SSSは情報理論的安全性をもっていたが、こちらは計算理論的安全性に低下する
まず、p, q は素数で,qは p − 1 がpで割り切れるような素数．g を $ Z^∗_p の位数 q の元とする．
① D は，各 $ 1 ≤ j ≤ t − 1 について，秘密かつ無作為に $ a_j ∈ Z_q を選び，
多項式 f(x) を以下のように定める
$ f(x) = s + a_1 x + a_2 x^2 + · · · + a_{t−1} x^{t−1} mod\;q
このとき，秘密 s について，$ s = f(0) であり、$ a_0 = s である
② D は安全な通信路を介して $ s_i = f(d_i) を$ U_i に送る
n 人のパーティはそれぞれ値$ f(1), ..., f(n) mod\;p を受け取る。
ここまではSSSと同じ
③shareを検証可能にするために、ディーラーは多項式P(x)の各係数のコミットメントを計算して公開する.
例えば、上記の多項式のコミットメントは以下のようになる
$ G_0=g^s mod\;p
$ G_1=g^{a_1}mod\;p
...
$ G_{t-1}=g^{a_{t-1}}mod\;p
一般化すると、D は，各 $ 0 ≤ j ≤ t − 1 に対して，$ G_j = g^{a_j} mod\;p を計算して公開する．
また、素数位数$ {\displaystyle p} の巡回群$ {\displaystyle \mathbb {G} } と、$ {\displaystyle \mathbb {G} }の生成元 $ {\displaystyle g} がシステムパラメーターとして公開される
離散対数問題より、$ G_jから$ a_jを求めることはできないので係数を隠したまま配布することができる
④各ユーザー$ U_iは以下の合同式を確認することにより、自分の部分情報が正しいかどうかを確認できる
$ g^{s_i}≡g^{f(d_i)}
$ ≡ g^{s+a_1d_i+a_2d_i^2+···+a_{t−1}d_i^{it−1}}
$ ≡ g^sg^{a_1d_i}g^{a_2{d_i}^2}· · · g^{a_{t−1}d_i^{t−1}}
$ ≡ G_0G_1^{d_i}G_2^{d_i^2}· · · G_{t−1}^{d_i^{t−1}}
$ ≡ ((· · ·((G_{t−1}^{d_i})G_{t−2})^{d_i}· · ·)G_1)^{d_i}G_0 (mod p)
この方式では，$ G_0 = g^s が公開されるので，離散対数問題が解けないという仮定の下でのみ，s は安全
どうゆう理屈でshareを検証できるの？
$ s_i = f(d_i)なので、modの結果も同じになるはずで、不正なshareが混ざっていたら合同式が成立しない
commitmnetはshareと違って、全ての係数について配布される?
yes
まとめると、$ U_iは$ s_i=f(d_i)mod\;pであるかの検証をコミットメントの総乗を以下のように展開して確認する
$ g^{s_i} ≡ G_0G_1^{d_i}G_2^{d_i^2}· · · G_{t−1}^{d_i^{t−1}}
$ ≡ g^sg^{a_1d_i}g^{a_2{d_i}^2}· · · g^{a_{t−1}d_i^{t−1}}
$ ≡ g^{s+a_1d_i+a_2d_i^2+···+a_{t−1}d_i^{it−1}}
$ ≡g^{f(d_i)}
コミットメントを使って次数の領域に多項式の形を復元してるのがポイント
⑤検証が通れば、SSSと同じようにラグランジュ補間公式で秘密を復元する.
3.Pedarson's VSS
まず、p, q は素数で,qは p − 1 がpで割り切れるような素数．g, h を $ Z^∗_p の位数 q の元とする．
① D は，各 0 ≤ j ≤ t − 1 について，秘密かつ無作為に $ a_j , b_j ∈ Z_q を選び，多項式 $ f_1(x), f_2(x) を以下のように定める．
$ f_1(x) = s + a_1 x + a_2 x^2 + · · · + a_{t−1} x^{t−1} mod q
$ f_2(x) = b_0 + b_1 x + b_2 x^2 + · · · + b_{t−1} x^{t−1} mod q
このとき，秘密$ s について，$ s = f_1(0) であり、$ a_0 = s である
②D は安全な通信路を介してshareのペア $ s_i = f_1(d_i), r_i = f_2(d_i) を$ U_i に送る
③D は，各 $ 0 ≤ j ≤ t − 1 について，コミットメント$ G_j = g^{a_j}h^{b_j} mod p を計算して公開する．
④Ui は以下の合同式を確認することにより，自分の部分情報が正しいかどうかを確認できる
$ g^{s_i}h^{r_i} ≡ g^{f_1(d_i)}h^{f_2(d_i)}
$ ≡ g^{a_0+a_1d_i+a_2d_i^2+···+a_{t−1}d_i^{t−1}}h^{b_0+b_1d_i+b_2d_i^2+···+b_{t−1}d_i^{t−1}}
$ ≡ (g^{a_0} h^{b_0})(g^{a_1d_i}h^{b_1d_i})(g^{a_2d_i^2}h^{b_2d_i^2})· · ·(g^{a_{t−1}d_i^{t−1}}h^{b_{t−1}d_i^{t−1})}
$ ≡ (g^{a_0} h^{b_0})(g^{a_1} h^{b_1})^{d_i}(g^{a_2} h^{b_2})^{d_i^2}· · ·(g^{a_{t−1}} h^{b_{t−1}})^{d_i^{t−1}}
$ ≡ G_0G_1^{d_i}G_2^{d_i^2}· · · G_{t−1}^{d_i^{t−1}}
$ ≡ ((· · ·((G_{t−1}^{d_i})G_{t−2})^{d_i}· · ·)G_1)^{d_i}G_0 (mod p)
$ G_0 = g^sh^{b_0} が公開されるが，s に関する情報は全く漏れない
⑤検証が通れば、SSSと同じようにラグランジュ補間公式で秘密を復元する.(?)
なんで多項式二つ作った?
わからん！
参考文献